백준 14003번
오늘 풀어본 문제는 백준의 14003번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
수열 $A$ 가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 $A = {10, 20, 10, 30, 20, 50}$ 인 경우에 가장 긴 증가하는 부분 수열은 $A = {\textbf{10}, \textbf{20}, 10, \textbf{30}, 20, \textbf{50}}$ 이고, 길이는 $4$ 이다.
입력
첫째 줄에 수열 $A$ 의 크기 $N$ $(1 \leq N \leq 1,000,000)$ 이 주어진다.
둘째 줄에는 수열 $A$ 를 이루고 있는 $A_i$ 가 주어진다. $(-1,000,000,000 \leq Ai \leq 1,000,000,000)$
출력
첫째 줄에 수열 $A$ 의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.
풀이과정
1번째 시도
이 문제는 다이나믹 프로그래밍을 이용하여 해결해야 하는 문제이다. 기본 아이디어는 이전 수 들중 현재 수보다 작은 수들까지의 증가하는 부분 수열의 길이의 최댓값에 1을 더한 길이를 현재 수까지의 가장 긴 증가하는 부분 수열의 길이로 택하면 된다.
이 때 이전 수들을 확인하는 과정에서 전부 일일이 확인하게 되면 알고리즘의 전체 시간복잡도가 $O(n^2)$이 되어 시간초과가 발생하게 된다. 대신 $O(n \log n)$ 만에 끝내는 알고리즘이 있다.
그건 DP 배열에 수열의 수들을 저장할 때, 배열의 사이에 수를 대체하거나 맨끝에다가 수를 추가하는 방식으로 DP 배열을 업데이트 하는 것이다. 이 때 대체할 수를 찾는 과정에서 이분 탐색을 이용하기 때문에 전체 시간 복잡도가 $O(n \log n)$ 이 되는 것이다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<int> arr(1000000);
vector<int> dp;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, length;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
if (i == 0 || arr[i] > dp.back()) {
dp.emplace_back(arr[i]);
}
else {
int index = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
dp[index] = arr[i];
}
}
length = dp.size();
cout << length << "\n";
for (auto& i : dp) {
cout << i << " ";
}
return 0;
}
실행 결과 ‘틀렸습니다’가 나왔다.
2번째 시도
가장 긴 증가하는 부분 수열 (LIS) 의 길이는 제대로 출력하였지만, LIS 자체는 제대로 출력하지 못했기 때문에 ‘틀렸습니다’ 가 나온것이었다. 처음에는 별 생각없이 DP 배열을 그대로 출력하면 그것이 LIS가 될 것이라고 생각했지만, 업데이트 과정에서 LIS에 포함되지 않는 수들이 DP 배열에 들어갈 수 있다는 것을 알게되었다.
그래서 DP 배열을 업데이트 하는 과정에서 입력으로 주어진 배열의 각 원소가 DP 배열의 몇 번째 인덱스를 업데이트 하는지를 저장하도록 하였다. 그리고 std::stack 을 이용하여 인덱스를 역으로 추적하며 LIS를 완성시켰다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<int> arr(1000000);
vector<int> indexOfLIS(1000000);
vector<int> dp;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, length;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
if (i == 0 || arr[i] > dp.back()) {
dp.emplace_back(arr[i]);
indexOfLIS[i] = dp.size() - 1;
}
else {
int index = lower_bound(dp.begin(), dp.end(), arr[i]) - dp.begin();
dp[index] = arr[i];
indexOfLIS[i] = index;
}
}
length = dp.size();
cout << length << "\n";
stack<int> s;
int currentIndex = length - 1;
for (int i = N - 1; currentIndex >= 0; i--) {
if (indexOfLIS[i] == currentIndex) {
s.push(arr[i]);
currentIndex--;
}
}
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
return 0;
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
CLASS 4나 5 문제들은 DP를 활용하는 문제들이 많이 있는데, DP라는 용어로 퉁쳐서 그렇지 필요한 아이디와와 코드로 구현하는 방법들은 천차만별인 것 같다.
그런 다양한 경우에 대해서 아이디어들을 잘 떠올리고, 문제를 해결할 수 있음을 증명하고, 코드로 구현하는 3가지를 빠르고 정확하게 해내려면 많은 연습과 노력이 필요할 것 같다…
여담으로, 이 문제의 이름은 ‘가장 긴 증가하는 부분 수열 5’ 인데, 덕분에 2, 3, 4 문제들도 쉽게 풀렸다. 2, 3, 4 문제들은 5번 문제에 비해 조건이 완화된 문제들이었기 때문에 코드를 그대로 제출하거나 출력하는 부분 몇 개만 지워도 통과가 되었다. 이런 ‘날먹’은 꽤 짜릿한 것 같다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/14003